package test;

import java.util.Arrays;

/**
 * 描述：随机快排
 *
 * @author hl
 * @date 2021/7/25 11:38
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {100,3,200,2,1,4};
        QuickSort main = new QuickSort();
        main.quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public void quickSort(int[] arr){
        if (arr == null || arr.length == 0) {
            return ;
        }
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int l, int r) {
        if (l >= r) {
            return ;
        }
//        swap(arr, (int) (l + ((r - l + 1) * Math.random())), r);
        swap(arr, (int) (l + (Math.random() * (r - l + 1))), r);
        int[] p = partion(arr, l, r);
        sort(arr, l, p[0] - 1);
        sort(arr, p[1] + 1, r);
    }
//private void sort(int[] arr, int l, int r) {
//    if (l < r) {
//        swap(arr, (int) (l + (Math.random() * (r - l + 1))), r);//随机快排（随机选一个数进行）
//        int[] p = partion(arr, l, r);
//        sort(arr,l,p[0] - 1);
//        sort(arr,p[1] + 1,r);
//    }
//}

    private int[] partion(int[] arr, int l, int r) {
        int less = l - 1, more = r;
        while(l < more){
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            }else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            }else{
                l++;
            }
        }
        swap(arr, more, r);
        return new int[]{less + 1, more};
    }


    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
